package 剑指Offer._5160;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/22 15:06
 * 队列的最大值
 * 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
 * 若队列为空，pop_front 和 max_value 需要返回 -1
 * 算法：队列
 * 如果最大的数还在队列中，就要把这个最大的数保存起来
 * 如果这个数出队列了，那么就要把保存的这个数移除，获取下一个最大的数
 */
public class _59II {

    class MaxQueue {
        Deque<Integer> queue, maxQueue;

        public MaxQueue() {
            queue = new ArrayDeque<>();
            maxQueue = new ArrayDeque<>();
        }

        public int max_value() {
            if (maxQueue.isEmpty()) return -1;
            return maxQueue.peek();
        }

        public void push_back(int value) {
            queue.offer(value);
            while (!maxQueue.isEmpty() && value > maxQueue.peekLast()) maxQueue.pollLast();
            maxQueue.offer(value);
        }

        public int pop_front() {
            if (queue.isEmpty()) return -1;
            final Integer poll = queue.poll();
            if (poll.equals(maxQueue.peek())) maxQueue.poll();
            return poll;
        }
    }

}
